// https://leetcode.cn/problems/unique-binary-search-trees-ii/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

/**
 二叉搜索树的特点是顶层节点永远比左侧节点大

 */
#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector <vector<vector < TreeNode * >>>
    cache;

    vector<TreeNode *> generateTrees(int n) {
        cache.resize(n, vector < vector < TreeNode * >> (n));
        return create1(1, n);
    }

    // 参考自 https://leetcode.cn/problems/unique-binary-search-trees-ii/solution/he-qian-mian-man-er-cha-shu-de-ti-ting-xiang-de-by/
    vector<TreeNode *> create(int start, int end) {
        cout << "start:" << start << ",end:" << end << endl;
        if (start > end) return {nullptr};
        vector < TreeNode * > res;
        for (int i = start; i <= end; i++) {
            for (auto &l : create(start, i - 1)) {
                for (auto &r : create(i + 1, end)) {
                    TreeNode *head = new TreeNode(i, l, r);
                    res.push_back(head);
                }
            }
        }
        return res;
    }

    vector<TreeNode *> create1(int start, int end) {
        if (start > end) return {nullptr};
        if (!cache[start][end].empty()) {
            return cache[start][end];
        }
        vector < TreeNode * > res;
        for (int i = start; i <= end; i++) {
            for (auto &l : create1(start, i - 1)) {
                for (auto &r : create1(i + 1, end)) {
                    TreeNode *head = new TreeNode(i, l, r);
                    res.push_back(head);
                }
            }
        }
        cache[start][end] = res;
        return res;
    }


    void show(TreeNode *node) {
        if (node) {
            cout << node->val << ",";
            show(node->left);

            show(node->right);
        } else {
            cout << "null,";
        }
    }
};

int main() {
    Solution so;
    int n = 3;
    vector < TreeNode * > res = so.generateTrees(n);
    cout << "size: " << res.size() << endl;
    for (int i = 0; i < res.size(); i++) {
        cout << "i:" << res[i]->val << endl;
        so.show(res[i]);
        cout << endl;
    }
    return 0;
}
